import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

// 插入、删除和获取随机元素O(1)时间且允许有重复数字的结构
// 测试链接 :
// https://leetcode.cn/problems/insert-delete-getrandom-o1-duplicates-allowed/
public class InsertDeleteRandomDuplicatesAllowed {

    class RandomizedCollection {

        public HashMap<Integer, HashSet<Integer>> map;
        public ArrayList<Integer> arr;

        public RandomizedCollection() {
            map = new HashMap<>();
            arr = new ArrayList<>();
        }

        public boolean insert(int val) {
            int index = arr.size(); //数组加入的值的下标

            //从map中取出set,如果map中，没有val,则new一个返回set
            HashSet<Integer> set = map.getOrDefault(val, new HashSet<>());
            set.add(index);
            arr.add(val);
            map.put(val,set);
            return set.size() == 1;  //第一次插入返回true
        }

        public boolean remove(int val) {
            if(!map.containsKey(val)) {
                return false;  //不存在返回false;
            }
            //下面表示这个val存在

            HashSet<Integer>  set = map.get(val);  //从map中拿出key
            int valIndex = set.iterator().next();  //拿出要删除数的下标
            int endValue = arr.get(arr.size()-1);  //找到最后一个数的值

            if(val == endValue) { //要删除的数等于数组最后一个数   那就直接删除数组最后一个数的下标
                set.remove(arr.size()-1);
            }else{
                arr.set(valIndex,endValue);   //最后一个数覆盖被删除的数
                HashSet<Integer> endSet=map.get(endValue);  //数组最后一个数所对应的key
                endSet.remove(arr.size()-1);
                endSet.add(valIndex);
                set.remove(valIndex);
            }
            arr.remove(arr.size()-1);
            if(set.isEmpty()){
                map.remove(val);
            }

            return true;
        }

        public int getRandom() {
            return arr.get( (int) ( Math.random() * arr.size() ) );
        }
    }
}
